package com.zzy.algorithm.tree;

import com.zzy.algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * LeetCode - 145 ： 后续遍历
 *
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 */
public class Q20_LRD_PostorderTraversal {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Q20_LRD_PostorderTraversal q20_lrd_postorderTraversal = new Q20_LRD_PostorderTraversal();
        q20_lrd_postorderTraversal.soution(TreeNode.treeNode1,list);
//        q20_lrd_postorderTraversal.recurse(TreeNode.treeNode1,list);
        for (int i = 0 ; i < list.size() ; i++){
            System.out.println(list.get(i));
        }
    }

    /**
     * 迭代
     * @param root
     * @param list
     */
    private void soution(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = root;
        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == prev){
                list.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
    }

    /**
     * 递归
     * @param root
     * @param list
     */
    private void recurse(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        recurse(root.left,list);
        recurse(root.right,list);
        list.add(root.val);
    }
}
